#include <iostream>
using namespace std;
#include <vector>

// N = 7 
// START = 2
// AIM = 4
// K = 4 

int process1(int cur , int rest , int aim , int n)
{
  if (rest == 0)
  {
    return cur == aim ? 1 : 0;
  }

  if (cur == 1)
  {
    return process1(2 , rest -1 , aim , n);
  }

  if (cur == n)
  {
    return process1(n-1 , rest-1 , aim , n);
  }

  return process1(cur-1 , rest-1 , aim , n) 
    + process1(cur+1 , rest-1 , aim , n);
}




int _process2(int cur , int rest , int aim , int n , vector<vector<int>>& dp)
{
  if (dp[cur][rest] != -1)
  {
    return dp[cur][rest];
  }

  int ans = 0;
  if (rest == 0)
  {
    ans = cur == aim ? 1 : 0;
  }
  else if (cur == 1)
  {
    ans = _process2(2 , rest-1 , aim , n , dp);
  }
  else if (cur == n)
  {
    ans = _process2(n-1 , rest-1 , aim , n , dp);
  }
  else 
  {
    ans = _process2(cur -1  , rest -1 , aim , n , dp ) 
      + _process2(cur +1 , rest -1 , aim , n , dp);
  }

  dp[cur][rest] = ans;
  return ans;
}


int process2(int cur , int rest , int aim , int n)
{
  vector<vector<int>> dp(n + 1 , vector<int>(rest + 1));
  for (int i = 0 ; i < n + 1 ; i++ )
  {
    for (int j = 0; j < rest + 1 ; j++)
    {
      dp[i][j] = -1;
    }
  }

  return  _process2( cur ,  rest ,  aim ,  n , dp);
}

int process3(int cur , int rest , int aim , int n)
{
  vector<vector<int>> dp(n + 1 , vector<int>(rest + 1));
  for (int i = 0 ; i < n + 1 ; i++ )
  {
    for (int j = 0; j < rest + 1 ; j++)
    {
      dp[i][j] = 0;
    }
  }

  // row 1
  dp[aim][0] = 1;


  for (int r = 1 ; r <= rest ; r++)
  {
    dp[1][r] = dp[2][r-1];

    for (int c = 2 ; c < n ; c++)
    {
      dp[c][r] = dp[c-1][r-1] + dp[c+1][r-1];
    }

    dp[n][r] = dp[n-1][r-1];
  }


  return dp[cur][rest];
}


int main()
{
  int ret = process3(2 , 6 , 4 , 5);
  cout << ret << endl;
  return 0;
}
